package com.essential.array;


import java.util.Arrays;

/*
##冒泡排序法
    常用的排序算法有冒泡排序、插入排序和快速排序等
    冒泡排序的特点是，每一轮循环后，最大的一个数被交换到末尾，因此，下一轮循环就可以“刨除”最后的数，每一轮循环都比上一轮循环的结束位置靠前一位。
    注意到交换两个变量的值必须借助一个临时变量。
##标准库排序
    Arrays.sort()
##小结
    常用的排序算法有冒泡排序、插入排序和快速排序等；
    冒泡排序使用两层for循环实现排序；
    交换两个变量的值需要借助一个临时变量。
    可以直接使用Java标准库提供的Arrays.sort()进行排序；
    对数组排序会直接修改数组本身。

 */
public class SortArray {
    public static void main(String[] args) {
        //冒泡排序
        //注意到交换两个变量的值必须借助一个临时变量。
        int[] ns = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
        // 排序前:
        System.out.println(Arrays.toString(ns));
        for (int i = 0; i < ns.length - 1; i++) {
            for (int j = 0; j < ns.length - i - 1; j++) {
                if (ns[j] > ns[j+1]) {
                    // 交换ns[j]和ns[j+1]:
                    int tmp = ns[j];
                    ns[j] = ns[j+1];
                    ns[j+1] = tmp;
                }
            }
        }
        // 排序后:
        System.out.println(Arrays.toString(ns));

        //标准库排序
        int[] ns1 = { 28, 12, 89, 73, 65, 18, 96, 50, 8, 36 };
        Arrays.sort(ns1);
        System.out.println(Arrays.toString(ns1));
    }
}
/*
必须注意，对数组排序实际上修改了数组本身。例如，排序前的数组是：

int[] ns = { 9, 3, 6, 5 };
在内存中，这个整型数组表示如下：

      ┌───┬───┬───┬───┐
ns───>│ 9 │ 3 │ 6 │ 5 │
      └───┴───┴───┴───┘
当我们调用Arrays.sort(ns);后，这个整型数组在内存中变为：

      ┌───┬───┬───┬───┐
ns───>│ 3 │ 5 │ 6 │ 9 │
      └───┴───┴───┴───┘
即变量ns指向的数组内容已经被改变了。

如果对一个字符串数组进行排序，例如：

String[] ns = { "banana", "apple", "pear" };
排序前，这个数组在内存中表示如下：

                   ┌──────────────────────────────────┐
               ┌───┼──────────────────────┐           │
               │   │                      ▼           ▼
         ┌───┬─┴─┬─┴─┬───┬────────┬───┬───────┬───┬──────┬───┐
ns ─────>│░░░│░░░│░░░│   │"banana"│   │"apple"│   │"pear"│   │
         └─┬─┴───┴───┴───┴────────┴───┴───────┴───┴──────┴───┘
           │                 ▲
           └─────────────────┘
调用Arrays.sort(ns);排序后，这个数组在内存中表示如下：

                   ┌──────────────────────────────────┐
               ┌───┼──────────┐                       │
               │   │          ▼                       ▼
         ┌───┬─┴─┬─┴─┬───┬────────┬───┬───────┬───┬──────┬───┐
ns ─────>│░░░│░░░│░░░│   │"banana"│   │"apple"│   │"pear"│   │
         └─┬─┴───┴───┴───┴────────┴───┴───────┴───┴──────┴───┘
           │                              ▲
           └──────────────────────────────┘
原来的3个字符串在内存中均没有任何变化，但是ns数组的每个元素指向变化了。
 */